package com.ljy.my_study.leetcode.魔术索引;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.TreeSet;

/**
 * @author lijunying
 * @date 2020/7/31 14:50
 */
public class TestMain {

//    魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。
//    给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，
//    如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。
//
//    示例1:
//
//    输入：nums = [0, 2, 3, 4, 5]
//    输出：0
//    说明: 0下标的元素为0
//    示例2:
//
//    输入：nums = [1, 1, 1]
//    输出：1
//    说明:
//
//    nums长度在[1, 1000000]之间
//    此题为原书中的 Follow-up，即数组中可能包含重复元素的版本

    public static void main(String[] args) {
        TreeSet<int[]> set=new TreeSet<>((a,b)->{
            int value=a[1]-b[1];
            if(value!=0){
                return value;
            }
            return b[0]-a[0];
        });
        set.add(new int[]{2,2});
        set.add(new int[]{1,2});
        set.add(new int[]{3,2});
        int[][] a=new int[][]{{3,1},{3,3},{5,2}};
        int[] result=set.ceiling(new int[]{3,1});
        result=set.ceiling(new int[]{3,3});
        result=set.ceiling(new int[]{5,2});
        result=set.ceiling(a[0]);
        System.out.println();

        PriorityQueue<Integer> queue=new PriorityQueue<>();
//        queue.
    }

    public int findMagicIndex(int[] nums) {
        int start=0;
        int end=nums.length;
        int index=-1;
        while(start<end){
            int mid=(start+end)/2;
            if(nums[mid]==mid){

            }
        }
        return -1;
    }

    private int doFindMagicIndex(int[] nums,int start,int end){
        while(start<end){
            int mid=(start+end)/2;
            if(nums[mid]==mid){
                int nextIndex=doFindMagicIndex(nums,start,mid);
                if(nextIndex==-1){
                    return mid;
                }else{
                    return nextIndex;
                }
            }
            if(nums[mid]<mid){

            }else{

            }
        }
        return -1;
    }
}
